# https://leetcode.cn/problems/number-of-digit-one/description/
# 233. 数字 1 的个数
# medium, 刘小康 2024.09.26
# 数位DP

class Solution:
    def countDigitOne(self, n: int) -> int:
        if n == 0:
            return 0

        num_s = str(n)
        flag = 0
        dp = [[0 for _ in range(len(num_s) + 1)] for __ in range(len(num_s))]
        # __init__
        for i in range(1, 10):
            if i >= int(num_s[0]):
                break

            if i == 1:
                dp[0][1] += 1
            else:
                dp[0][0] += 1
        if int(num_s[0]) == 1:
            flag += 1

        # dp
        for i in range(1, len(num_s)):
            for j in range(len(num_s) + 1):
                if j == 0:
                    dp[i][j] += 8 + dp[i - 1][j] * 9
                elif j == 1:
                    dp[i][j] += 1 + dp[i - 1][j - 1] + dp[i - 1][j] * 9
                else:
                    dp[i][j] += dp[i - 1][j - 1] + dp[i - 1][j] * 9
            for k in range(10):
                if k >= int(num_s[i]):
                    break

                if k == 1:
                    dp[i][flag + 1] += 1
                else:
                    dp[i][flag] += 1
            if int(num_s[i]) == 1:
                flag += 1

        # res
        res = 0
        for i in range(1, len(num_s) + 1):
            res += dp[-1][i] * i
        return res + flag
